#ifndef _PRIQUEUE_HPP_
#define _PRIQUEUE_HPP_

#include <vector>
#include <map>
#include <iostream>
using namespace std;

inline int themin(int a, int b){
    return (a < b) ? a : b;
}

template <typename uni,typename comp>
struct DataBase{
    uni key;
    comp data;
};

template <typename uni, typename comp>
class PriorityQueue{
private:
//public:
    // Define the nodes
    vector<struct DataBase<uni, comp> > node;
    // Define unorder map
    unordered_map<uni, int> pqfind;
    // swap func
    void nswap(DataBase<uni, comp> &pa, DataBase<uni, comp> &son){
        DataBase<uni, comp> temp = pa;
        pa = son;
        son = temp;
        int loc = pqfind[pa.key];
        pqfind[pa.key] = pqfind[son.key];
        pqfind[son.key] = loc;
    }
    // Heaplize func
    void upgo(int index){
        while(index>1){
            if(node[index/2-1].data<node[index-1].data)
                break;
            nswap(node[index / 2 - 1], node[index - 1]);
            index /= 2;
        }
    }

    void downgo(int index){
        while(index<=node.size()){
            if(2*index+1<=node.size()){
                if(node[2*index-1].data<node[2*index].data){
                    if(node[index-1].data<node[2*index-1].data)
                        break;
                    nswap(node[index - 1], node[2*index - 1]);
                    index = 2*index ;
                }else{
                    if(node[index-1].data<node[2*index].data)
                        break;
                    nswap(node[index - 1], node[2*index]);
                    index = 2*index + 1;
                }
            }else if(2*index<=node.size()){
                if(node[index-1].data<node[2*index-1].data)
                    break;
                nswap(node[index - 1], node[2*index - 1]);
                index = 2*index ;
            }else
                break;
        }
    }

public:
    void insert(DataBase<uni,comp> & _x){
        node.push_back(_x);
        pqfind[_x.key] = node.size();
        upgo(node.size());
    }

    const DataBase<uni,comp> & top(){
        return node[0];
    }

    bool empty(){
        return node.empty();
    }

    int find(const uni & key){
        int ans = pqfind[key];
        if(ans == 0){
            cout << "The node with key: " << key << " does not exist." << endl;
            return 0;
        }else
            return ans;
    }

    void deleteMin(){
        if(node.empty()){
            cout << "Heap is empty!" << endl;
            return;
        }
        uni del = node[0].key;
        nswap(node[0], node[node.size() - 1]);
        node.pop_back();
        pqfind.erase(del);
        downgo(1);
    }

    void buildHeap(const std::vector<DataBase<uni, comp> > & _input){
        if(!node.empty()){
            cout << "Heap has been built !" << endl;
            return;
        }else{
            for (int i = 0; i < _input.size();i++){
                node.push_back(_input[i]);
                pqfind[node[i].key] = i + 1;
            }
            int k=1;
            while (k <= node.size())
                k <<= 1;
            while(k>1){
                for (int i = k; i < themin(2 * k, node.size() + 1); i += 2)
                    downgo(i/2);
                k /= 2;
            }
        }
    }

    void remove(uni k){
        int index = find(k);
        if(index == 0)
            return;
        else{
            nswap(node[index - 1], node[node.size() - 1]);
            node.pop_back();
            pqfind.erase(k);
            upgo(index);
            downgo(index);
        }
    }

    void modifyData(uni k, comp d){
        int index = find(k);
        if(index == 0){
            return;
        }
        else{
            node[index - 1].data += d;
            upgo(index);
            downgo(index);
        }
    }
    void Print(){
        int k = 2;
        for (int i = 0; i < node.size(); i++){
            cout << node[i].data << ' ';
            if(i+2==k){
                k <<= 1;
                cout << endl;
            }
        }
        cout << endl;
    }

    void PrintKey(){
        int k = 2;
        for (int i = 0; i < node.size(); i++){
            cout << node[i].key << ' ';
            if(i+2==k){
                k <<= 1;
                cout << endl;
            }
        }
        cout << endl;
    }
};

#endif